﻿#define NEW
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using VersionComparer.Comparer;
using VersionComparer.Configuration;


namespace VersionComparer.DataModel
{
    public class ItemMatcher
    {
        #region inner classes
        [DebuggerDisplayAttribute ("{DebugText}")]
        public class ItemMatch
        {
            public ComparableItem Root
            {
                get;
                private set;
            }
            public ItemMatch(ComparableItem root1, ComparableItem item1, ComparableItem item2, double bestMatch, int index)
            {
                BestMatch = bestMatch;
                Root = root1;
                Item1 = item1;
                Item2 = item2;
                Index = index;
            }
            public int Index
            {
                get;
                private set;
            }
            public double BestMatch
            {
                get;
                private set;
            }
            public string DebugText
            {
                get
                {
                    return string.Format("Index:{0}, BestMatch:{1}, Text:{2}", Index, BestMatch, Item1.FullText);
                }
            }
            public static int Compare(ItemMatch item1, ItemMatch item2)
            {
                if (item1.BestMatch == item2.BestMatch)
                    return item2.Index.CompareTo(item1.Index);
                else
                    return item2.BestMatch.CompareTo(item1.BestMatch);
            }
            public ComparableItem Item1 { get; set; }
            public ComparableItem Item2 { get; set; }
        }

        #endregion inner classes

        #region fields
        List<ComparableItem> items1 = new List<ComparableItem>();
        List<ComparableItem> items2 = new List<ComparableItem>();
        #endregion fields

        #region constructors
        public ItemMatcher(ComparisonAlgorithm algorithm, ComparableItem root , ComparableItem parentItem1, ComparableItem parentItem2)
        {
            Algorithm = algorithm;
            Root = root;
            ParentItem1 = parentItem1;
            ParentItem2 = parentItem2;
        }
        #endregion constructors

        #region properties
        public int Count
        {
            get
            {
                return Matches.Length;
            }
        }

        public ItemMatch[] Matches
        {
            get;
            private set;
        }
        
        public ComparableItem Root
        {
            get;
            private set;
        }
        ComparableItem ParentItem1
        {
            get;
            set;
        }
        ComparableItem ParentItem2
        {
            get;
            set;
        }
        #endregion properties

        public void AddSourceItem(ComparableItem item)
        {
            items1.Add(item);
        }
        public void AddDestinationItem(ComparableItem item)
        {
            items2.Add(item);
        }
        protected virtual ComparableItem CreateEmptyItem(ComparableItem parent, ComparableItem otherItem)
        {
            ComparableItem newItem = Activator.CreateInstance(otherItem.GetType()) as ComparableItem;
            newItem.Exists = false;
            newItem.Text = otherItem.Text;
            newItem.Parent = parent;
            newItem.RelatedItem = otherItem;
            return newItem;
        }

        ComparisonAlgorithm Algorithm
        {
            get;
            set;
        }
            
        public virtual void Match()
        {
            int items1Count = items1.Count;
            List<ItemMatch> matches = new List<ItemMatch>(Math.Max ( items1.Count , items2.Count));
            List<ComparableItem> finalList = new List<ComparableItem>(items1);
            List<ComparableItem> destinationList = items2;
            Dictionary<int, List<int>> hashcodes = new Dictionary<int, List<int>>();
           
            FindDirectMatches(items1Count, destinationList, hashcodes);

            #region fast comparison to exclude direct matches

            for (int item1Index = 0; item1Index < items1.Count; item1Index++)
            {
                ComparableItem item1 = items1[item1Index];
                if (item1.RelatedItem != null)
                {
                    matches.Add(new ItemMatch(Root, item1, item1.RelatedItem, 1, matches.Count));
                }
                else
                {
                    double bestMatch = 0;
                    int index = -1;
                    List<int> values;
                    bool found = false;
                    if (hashcodes.TryGetValue(item1.MatchHashCode, out values))
                    {
                        for (int i = 0; i < values.Count; i++)
                        {
                            index = values[i];
                            var item2 = items2[index];
                            double match = item1.Matches(Algorithm , item2);

                            if (match == 1)
                            {
                                item2.RelatedItem = item1;
                                values.RemoveAt(i);
                                matches.Add(new ItemMatch(Root, item1, item2, 1, matches.Count));
                                found = true;
                                break;
                            }
                            else
                            {
                                if (match > bestMatch)
                                    bestMatch = match;
                            }
                        }
                    }
                    if (!found)
                        matches.Add(new ItemMatch(Root, item1, null, bestMatch, matches.Count));
                }
            }
            #endregion fast comparison to exclude direct matches

            destinationList.RemoveAll(x => x.RelatedItem != null);
            FuzzyMatch(matches, destinationList);

            #region build final sorted list
            foreach (var item2 in destinationList)
                matches.Add(new ItemMatch(Root, CreateEmptyItem(ParentItem1, item2), item2, 0, matches.Count));
            #endregion build final sorted list
            Matches = matches.ToArray();
            
        }

        private void FindDirectMatches(int items1Count, List<ComparableItem> destinationList, Dictionary<int, List<int>> hashcodes)
        {
            for (int i = 0; i < items2.Count; i++)
            {
                var item2 = destinationList[i];
                if (i < items1Count && item2.Matches(Algorithm, items1[i]) == 1)
                {
                    var item1 = items1[i];
                    item1.RelatedItem = item2;
                    item2.RelatedItem = item1;
                }
                else
                {
                    int hash = item2.MatchHashCode;
                    List<int> value;
                    if (!hashcodes.TryGetValue(hash, out value))
                    {
                        value = new List<int>();
                        hashcodes.Add(hash, value);
                    }
                    value.Add(i);
                }
            }
        }

        private void FuzzyMatch(List<ItemMatch> unsortedMatches, List<ComparableItem> destinationList)
        {
            #region slower, more thorough comparison to find best fits

            var algorithm = Algorithm;
            int complexityThreshold = 100;
            if (algorithm == ComparisonAlgorithm.Auto)
            {
                if (unsortedMatches.Count * destinationList.Count > complexityThreshold)
                    algorithm = ComparisonAlgorithm.Fast;
                else
                    algorithm = ComparisonAlgorithm.Thorough;
            }
            List<ItemMatch> matches = new List<ItemMatch>(unsortedMatches);
            matches.Sort(ItemMatch.Compare);

            //sort the list so that we are able to do binary searches
            destinationList.Sort(Root);


            switch (algorithm)
            {
                case ComparisonAlgorithm.Thorough:
                    ThoroughFuzzy(destinationList, matches);

                    break;
                default:
                    FastFuzzy(destinationList, matches);
                    break;
            }
            #endregion slower, more thorough comparison to find best fits
        }

        private void ThoroughFuzzy(List<ComparableItem> destinationList, List<ItemMatch> matches)
        {
            //this algorithm is not optimal in terms of results - but it is more performant than the alternative of exaustively checking all combinations looking for absolute best fit
            for (int item1Index = 0; item1Index < matches.Count; item1Index++)
            {
                var itemMatch = matches[item1Index];
                if (itemMatch.Item2 == null)
                {
                    ComparableItem item1 = matches[item1Index].Item1;
                    double bestFit = DataModel.Match.NoMatch;
                    int bestFitIndex = -1;
                    for ( int destinationIndex = 0 ; destinationIndex < destinationList.Count ; destinationIndex ++)
                    {
                        double fit = item1.Matches(Algorithm, destinationList[destinationIndex]);
                        if (fit > bestFit )
                        {
                            bestFit = fit;
                            bestFitIndex = destinationIndex;
                        }
                    }
                    if ( bestFit != DataModel.Match.NoMatch )
                    {
                        itemMatch.Item2 = destinationList[bestFitIndex ];
                        destinationList.RemoveAt(bestFitIndex );
                    }
                    if (itemMatch.Item2 == null)
                        itemMatch.Item2 = CreateEmptyItem(ParentItem2, item1);
                }

            }
        }


        private void FastFuzzy(List<ComparableItem> destinationList, List<ItemMatch> matches)
        {
            //this algorithm is not optimal in terms of results - but it is more performant than the alternative of exaustively checking all combinations looking for absolute best fit
            for (int item1Index = 0; item1Index < matches.Count; item1Index++)
            {
                var itemMatch = matches[item1Index];
                if (itemMatch.Item2 == null)
                {
                    ComparableItem item1 = matches[item1Index].Item1;
                    if (destinationList.Count > 0)
                    {
                        int index = destinationList.BinarySearch(item1, Root);
                        if (index >= 0)
                        {
                            var item2 = destinationList[index];
                            if (item1.Matches(Algorithm, item2) != DataModel.Match.NoMatch)
                            {
                                itemMatch.Item2 = item2;
                                destinationList.RemoveAt(index);
                            }
                        }
                        else
                        {
                            index = ~index;
                            for (int i = Math.Max(index - 1, 0); i < destinationList.Count && i <= index; i++)
                            {
                                var item2 = destinationList[i];
                                //if (Math.Abs(item1.CompareTo(item2)) < 2)
                                if (item1.Matches(Algorithm, item2) != DataModel.Match.NoMatch)
                                {
                                    itemMatch.Item2 = item2;
                                    destinationList.RemoveAt(i);
                                    break;
                                }
                            }
                        }
                    }
                    if (itemMatch.Item2 == null)
                        itemMatch.Item2 = CreateEmptyItem(ParentItem2, item1);
                }

            }
        }
    }
}
